Curious Properties of an Iterative Process

Ryohei Miyadera
Hiroaki Simoda
Hiroki Takebayashi
Naoya Urakawa
Kousuke Morimoto
Koichi Tukiyama
Daisuke Minematu
Satoshi Hashiba

Kwansei Gakuin high school,
Nishinomiya city, Japan

Miyadera127@aol.com
miyadera1272000@yahoo.co.jp

Introduction:

This paper is based on a joint research of a mathematician and high school students.  You may wonder how high school students can do a research of mathematics, but a good combination of creativity of high school students and strict logic of experienced mathematician could produce many mathematicics theorems.

\(At\ the\ International\ Mathematica\ Syposium\ 2003\ Professor\ Robert\ Cowen\ gave\ us\ his\ book'\ Discovering\ Mathematics\ with\ Mathematica' . \ \ In\ this\ book\ he\ writes\ about\ the\ DCS\ problem . \ \ Let\ me\ introduce\ the\ DCS\ problem . \ \ 
Start\ with\ any\ positive\ integer\ n\ , \ 
    separately\ form\ the\ cube\ of\ each\ digit\ of\ n\ and\ let\ dcs[n] 
      denote\ the\ sum\ of\ the\ digit\ cubes . \ \ Replace\ \ n\ \ by\ dcs[
        n]\ and\ reapply\ the\ digit\ cube\ sum\ function . 
For\ Example, \ 
    start\ with\ \ n = \ \(12. \ \ dcs[12] = \(1\^3 + 2\^3 = 
          9. \)\)\)
\(\(dcs\^2\)[
          12] = \(dcs[
            9] = \(9\^3 = \(729. \ \ \ \(dcs\^3\)[12] = \(\(dcs\^2\)[
                  9] = \(dcs[729] = \(7\^3 + 2\^3 + 9\^3 = 
                    1080. \ \ \ Continue\ this\ operation\ and\ we\ get\)\)\)\)\)\)\) 
\(12 -> \(9 -> \(729 -> \(1080 -> ⋯\)\)\)\)
\(We\ studied\ this\ DCS\ process\ in\ our\ class\ and\ learned\ that\ this\ kind\ of\ simple\ process\ could\ be\ a\ very\ interesting\ subject\ of\ mathematics . \ \ After\ that\ students\ were\ encouraged\ to\ propose\ their\ own\ original\ processes . \ \ Two\ students\ proposed\ \ a\ new\ digits\ sum\ process\), and we began to investigate the process .   To our joy this process turned out to be very interesting .  
We named our process the dsf process .   We define  the dsf function by  dsf[n]= (Subscript[((Subscript[n, 1])^n), 1]) + (Subscript[((Subscript[n, 2])^n), 2]) + ⋯(Subscript[((Subscript[n, m])^n), m]),where  {(Subscript[n, 1]), (Subscript[n, 2]), ⋯, (Subscript[n, m]) } is \(TraditionalForm\`\(\(\ \ \)\(\(the\)\(\ \ \)\(list\)\(\ \)\(of\)\(\ \)\(the\)\(\ \)\(digits\)\(\ \)\(of\)\(\ \)\(an\)\(\ \)\(integer\)\(\ \)\)\)\)n  .    Suppose we start with any positive integer  n, and   repeatedly apply the function  dsf,then  we can generate a sequence of integers { (dsf^m)[n],n = 1,2,⋯}.  
      We found some very curious facts in this process .   This process is interesting from the view point of mathematicians, \(but\ this\ is\ also\ very\ interesting\ from\ the\ view\ point\ of\ mathematics\ education\),too,\(because\ this\ shows\ the\ possibility\ of\ a\ research\ by\ high\ school\ students\ when\ they\ can\ use\ a\ good\ software\ and\ have\ a\ proper\ problem . \ \ In\ our\ case\ students\ could\ \ make\ the\ best\ of\ the\ power\ of\ Mathematica\), \(and\ they\ could\ be\ very\ creative . \ \ \ Our\ research\ was\ inspired\ by\ \ \ \ Robert\ Cowen\ \ and\ John\ W . 
          Kennedy\ \ \ [
            1] . \ \ We\ want\ to\ thank\ them\ for\ their\ fascinating\ book . 
In\ this\ paper\ we\ prove\ some\ theorems\ using\ mathematics\), \(but\ we\ prove\ other\ theorems\ by\ the\ calculation\ of\ Mathematica . \ \ When\ we\ use\ Mathematica\ to\ prove\ theorems\), \(we\ try\ to\ write\ down\ the\ details\ of\ algorithms\ for\ the\ reader\ to\ check\ the\ correctness\ of\ \(\(calculation\)\(.\)\)\)

1. Mathematica  dsf  function  and the existance of a loop.

Througthout this paper we use the same function  dsf.  We define  dsf  by  dsf[n]= (Subscript[((Subscript[n, 1])^n), 1]) + (Subscript[((Subscript[n, 2])^n), 2]) + ⋯(Subscript[((Subscript[n, m])^n), m]),where  {(Subscript[n, 1]) (Subscript[n, 2]) ⋯(Subscript[n, m])}  is\(TraditionalForm\`\(\(\ \ \)\(\(the\)\(\ \ \)\(list\)\(\ \)\(of\)\(\ \)\(the\)\(\ \)\(digits\)\(\ \)\(of\)\(\ \)\(an\)\(\ \)\(integer\)\(\ \)\)\)\)n .

Example 1.   dsf[253]=(2^2) + (5^5) + (3^3)=3156.   (dsf^2)[253]= dsf[3156]=(3^3) + (1^1) + (5^5) + (6^6) = 49809.   Since (0^0) = 
                  1,(dsf^3)[253]= dsf[49809]=\(4\^4 + 9\^9 + 8\^8 + 0\^0 + 9\^9 = 
            791618451. \ \ In\ this\ way\ we\ can\ make\ a\ sequence\ of\ positive\ integers . \ 
                  253 -> \(3156 -> \(49809 -> \(791618451 -> ⋯\)\)\)\)

We are going to make the Mathematica function   dsf .

dsf[n_] := 
      Block[{m = n, t}, 
        t = IntegerDigits[
            m]; 
(∑_(k = 1)^(Length[t]))Max[1, t[[k]]]^t[[k]]]

\(\(\(\ \ \ \ \ \ \ \ \)\(Remark . \ \ In\ mathematics\ we\ usually\ define\ \ \ 0\^0 = 
      1, \ \(\(but\ Mathematica\ cannot\ calculate\ \ 0\^0 . \ \ Therefore\ we\ \ use\ Max[1, t[\([k]\)]]\^t[\([k]\)]\ to\ get\ \ 1\ when\ \ t[\([k]\)]\)\(=\)\(0.\)\(\ \)\)\)\)\)

Example  2.   Let's  start with n=13  and apply the function   dsf  71 times, then you get the following sequence.

NestList[dsf, 13, 71]

{13,28,16777220,2517295,388250291,420978083,421798753,405848204,33558331,16783575,18477236,18471246,17647933,389114542,404201375,827214,17601024,870463,17647699,776581633,18520794,405024635,53451,6534,50064,50039,387423643,17648012,17647678,19341414,387421287,35201810,16780376,18517643,17650825,17653671,1743552,830081,33554462,53476,873607,18470986,421845378,34381644,16824695,404294403,387421546,17651084,17650799,776537847,20121452,3396,387467199,793312220,388244100,33554978,405027808,34381363,16824237,17647707,3341086,16824184,33601606,140025,3388,33554486,16830688,50424989,791621836,405114593,387427281,35201810}

Remark.  As we can see easily  32th and 72th numbers are the same number  35201810.  Therefore we can conclude that this sequence  has a loop.

We are going to show that for any positive integer n  the sequence {(dsf^m)[n],m = 1,2,⋯} eventually will enter into a loop .   We need several theorems and lemmas to do that.

Example 3.   dsf[99999999999]<99999999999.   This is an example that for a sufficiently large number n  dsf[n]<n.

{dsf[99999999999], 99999999999} // N

Theorem 1. We have dsf[n]>n for n=2999999999, and we have dsf[n]<n  for n≥3000000000.
    We are going to prove this theorem by the following 5 Lemmas.

Lemma 1. For n=2999999999 we have dsf[n]>n.

Proof.  dsf[n]=9×(9^9) + (2^2) = 3486784405 > n.

Lemma 2. For a positive integer  n such that  3000000000  ≤ n  ≤  3999999999  we have  dsf[n]<n.

Proof .   Let  {(Subscript[n, 1]) = 3, (Subscript[n, 2]), ⋯, (Subscript[n, 10]) } be\(TraditionalForm\`\(\(\ \ \)\(\(the\)\(\ \ \)\(list\)\(\ \)\(of\)\(\ \)\(the\)\(\ \)\(digits\)\(\ \)\(of\)\(\ \)\(the\)\(\ \)\(integer\)\(\ \)\)\)\)n  . 
(1)  When the number of 9 in the list is exactly 9,then n = 3999999999.  dsf[n] = dsf[3999999999]=(3^3) + 
                9×(9^9) = 3486784428 < 
                  3999999999  =  n.

\(\((2)\)\ \ Suppose\ that\ the\ number\ of\ 9\ in\ the\ list\ is\ exactly\ 8. \ \ The\ remainning\ 2\ numbers\ are\ \ n\_1 = 
          3\ and\ a\ integer\ \ m\ such\ that\ \ m\ \  ≤ \ 8. \)
(α) When m  = 0 , then dsf[n] = 8×(9^9) + (3^3) + (0^0)  =  
              3099363940  < 3999999999  <  n
(β) When  1  ≤  
            m  ≥   8, then dsf[n] =8×(9^9) + (3^3) + (m^m)  <  
                8×(9^9) + (3^3) + (8^8)  =  
              3116141155  <  
                3199999999  ≤  n.

\(\((3)\)\ \ When\ the\ number\ of\ 9\ in\ the\ list\ is\ less\ than\ 8\), we have  dsf[n]<(3^3) + 7×(9^9) + 2×(8^8)=2745497882<3000000000  ≤n.

Lemma 3. For a positive integer n such that 4000000000≤n≤9999999999 we have dsf[n]<n.

Proof .   If  4000000000   ≤ n ≤  
        9999999999,dsf[n]≤10×(9^9)=3874204890 < n

Lemma 4.For a positive integer n such that 9999999999≤n≤99999999999 we have dsf[n]<n.

Proof .    For any number n such that 9999999999≤n≤99999999999  we have  dsf[n]≤11×(9^9)=4261625379 < n.

Lemma 5.    For a positive integer n such that  100000000000 ≤ n  we have   dsf[n]<n.

Proof .    If  {(Subscript[n, 1]), (Subscript[n, 2]), ⋯, (Subscript[n, m])}  is\(TraditionalForm\`\(\(\ \ \)\(\(the\)\(\ \ \)\(list\)\(\ \)\(of\)\(\ \)\(the\)\(\ \)\(digits\)\(\ \)\(of\)\(\ \)\(the\)\(\ \)\(integer\)\(\ \)\)\)\)n , then  m ≥ 11 and dsf[n]= (Subscript[((Subscript[n, 1])^n), 1]) + 
            (Subscript[((Subscript[n, 2])^n), 2]) + ⋯(Subscript[((Subscript[n, m])^n), m])  ≤  
          m×(9^9) .   Since m  ≥  11,m×(9^9) < 
        (10^(m - 1)) ≤ n.

Theorem 2. For any positive integer n  the sequence {(dsf^m)[n],m = 1,2,⋯} eventually will enter into a loop .   In other words there exist numbers  p  and  q  such that  (dsf^(p + kq + r))[n]= (dsf^(p + r))[n] for any positive integer  k  and any integer   r such that  0≤r≤q, where we call  q  the length of the loop .   The sequence  (dsf^m)[n] enters into a loop when n = p.

Proof .   If we start with a positive integer  n, we have a sequence  {(dsf^m)[n],m = 1,2,⋯} .  When  (dsf^m)[n]>3000000000, we have (dsf^m)[n]>(dsf^(m + 1))[n].  Therefore there exists a positive integer t such that  (dsf^(m + t))[n]<3000000000.  Therefore there are infinite number of m such that  (dsf^m)[n]<3000000000,\(and\ hence\ there\ is\ at\ least\ two\ positive\ integers\ \ \ v\ \ and\ \ w\ \ such\ that\ \ v\)  <  w  and  (dsf^v)[n]= (dsf^w)[n].  Therefore  {(dsf^v)[n],(dsf^(v + 1))[n],(dsf^(v + 2))[n],⋯,(dsf^(w - 1))[n]} is a loop.

2.  The length of loops.

The following function is the  Mathematica funcion findloop[ ]by which we can investigate the loop of the sequence  {(dsf^m)[n],m = 1,2  ⋯}.

Clear[dsf]; 
    dsf[n_] := Block[{m = n, t}, 
        t = IntegerDigits[
            m]; 
(∑_(k = 1)^(Length[t]))Max[1, t[[k]]]^t[[k]]]; 
    findloop[n_] := 
      Block[{m = n, u, dat}, dat = {m}; m = dsf[m]; 
        While[! MemberQ[dat, m], dat = Append[dat, m]; m = dsf[m]]; 
        dat = Append[dat, m]; 
        u = Flatten[Position[dat, Last[dat]]]; {n, u[[1]] - 1, Last[dat], 
          u[[2]] - u[[1]]}];

Example 4.  By findloop[17] we get  a list of numbers{17, 7, 34381644, 40} .   To understand the function  findloop  it is important to see the following table .   If  we start with the number 17, (dsf^m)[n] enters into a loop when m = 7, and  (dsf^7)[17] =34381644.  The length of the loop is 40 and (dsf^(7 + 40))[13]=34381644.

findloop[17]

Table[{n, Nest[dsf, 17, n]}, {n, 0, 47}]

The Mathematica function  findloop[n] returns   a list of numbers{n, p, t, q} .   We start with the number  n, then the sequence (dsf^m)[n] enters into a loop when m = p, and  (dsf^p)[n] =t .   The length of the loop is  q　and  (dsf^(p + q))[n]=t=(dsf^p)[n].

Example 5.  we are going to investigate the length of loops using the  function  findloop[].  We apply findloop[] to numbers 1 to 100, and found 3 kinds of lengths of loops, namely these of 1, 40 and 97. Note that we use findloop[][[4]]because we need only the length of the loops.

setofloops = Table[findloop[n][[4]], {n, 1, 100}]

Union[setofloops]

We applied findloop[ ] to a lot of numbers and found  8 types of loops.  By the following theorem we know that there are only 8 types of loops for any positive integer  n.  This is really fascinating fact!

Theorem 3.　For any positive integer  n  the sequence {(dsf^m)[n],m = 1,2  ⋯} eventually enters into one of the following 8 loops loop1A, loop1B, loop2, loop3, loop8, loop11, loop40 and loop97.
(1) loop1A = {1} with the length of 1.
(2) loop1B = {3435} with the length of 1.
(3) loop2 = {421845123,16780890} with the length of ２.
(4) loop3 = {16777500,2520413,3418} with the length of 3.
(5) loop8 = {809265896,⋯,792488396} with the length of 8.
(6) loop11 = {791621579,⋯,824599} with the length of 11.
(7) loop40 = {793312220,⋯,387467199} with the length of 40.
(8) loop97 = {1583236420,⋯,388290999} with the length of 97.
Remark. loop1A and loop1B are so called fixed points.　　
The proof of Theorem 3 is a little complicated, so if you find it difficult to understand this proof, please read the proof of Theorem 4 which is very similar to the proof of Theorem 3, but a lot more simple, because we do not have to use a complicated algorithm to prove Theorem 4.

We are going to prove Theorem 3 using Mathematica.  By Theorem 1 we only have to prove for a positive integer  n≤3000000000, but 3000000000 is quite a big number for us if we want to use Mathematica.  Therefore we have to find a good way to save time and memory we use.  The programs we used are a little bit complicated, but we used almost the same method in proving Theorem 4 in section 3.  If you think it difficult to understand the method used here, please read section 3 first.
    Our method depends on the following empirical fact about the dsf function.

An empirical fact.  Let  T be a set of numbers and  (dsf^m)[T]={(dsf^m)[n];n ∈ T}, then the size of (dsf^m)[T]as a set decreases as we make m bigger . 
This is an empirical fact, \(but\ it\ is\ as\ important\ as\ theorems\ in\ this\ paper . \ \ We\ are\ going\ to\ explain\ about\ this\ fact\ by\ \(\(examples\)\(.\)\)\)

Example 6. If we apply  the function  dsf  to the set of numbers T = {1, 2, ⋯, 10000} for 5 times,then the size of (dsf^5)[T]as a set is 554,so we could make the size of (dsf^5)[T]   (554/10000) =0.0554 of the original size of 10000. 
The following is the calculation and the result.

data1 = Union[Table[Nest[dsf, n, 5], {n, 1, 10000}]];

Length[data1]

Example 7.  If we apply dsf[] to the set of numbers  T ={10001, 10002, ⋯, 5110000} for 5 times,then the size of the set   (dsf^5)[T] is 2481,so we could make the size of the set  (dsf^5)[T](2481/5100000)//N =\(0.0004864705882352941`\ \ \ of\ the\ original\ size\ of\ T . 

            See\ the\ following\ \(\(calculation\)\(.\)\)\)

Do[
        Do[d[p] = 
            Union[Table[
                Nest[dsf, n, 5], {n, 1 + 10000  p, 10000 + 10000  p}]], {p, 
            10  q + 1, 10  q + 10}]; 
        sd[q] = Union[Flatten[Table[d[p], {p, 10  q + 1, 10  q + 10}]]], {q, 
          0, 50}];
Table[Length[sd[q]], {q, 0, 50}];
ssd = 
        Union[Flatten[
            Table[sd[q], {q, 0, 50}]]];
Length[ssd]

An explanation of the algorithm of the above program.

We applied the dsf function 5 times to the set of numbers  T.  The reason why we applied 5 times is that it seemed to us the best option in terms of time consumption.  We used Do[ ] and Table[ ] together, because it seemed to be the best option for our computer in terms of the size of memory and time consumption.  Table[ ] can calculate faster although it uses more memory, and Do[ ] is slower although it uses less memory.  Therefore we used the trial and error method by calculating a lot of numbers, and reached this option.  We are sure that our method is pretty good way to calculate, but not sure that ours is the best one.

When q = 0       and  p = 1   d[1] is the set of  Nest[dsf,n,5]  for n = 10001~ 20000
                               p = 2    d[2] is the set of  Nest[dsf,n,5] for  n = 20001~ 30000
                               p = 3    d[3] is the set of  Nest[dsf,n,5] for  n = 30001~ 40000
                                                            ⋮
                               p = 10  d[10] is the set of  Nest[dsf,n,5] for n = 100001 ~ 110000
                         sd[0] is the union of d[1], d[2],  ⋯, d[10]  
                         Therefore sd[0]   is the set  of  Nest[dsf,n,5] for n = 10001 ~ 110000
When q = 1       and  p =  11  d[11] is the set of  Nest[dsf,n,5]  for  n = 110001~ 120000
                               p =  12   d[12] is the set of  Nest[dsf,n,5]  for  n = 120001~ 130000
                               p =  13   d[13] is the set of  Nest[dsf,n,5]  for n = 130001~ 140000
                                                              ⋮
                               p =  20   d[20] is the set of  Nest[dsf,n,5]  for n = 200001 ~ 210000
                         sd[1] is the union of d[11], d[12],  ⋯, d[20]  
                         Therefore sd[1]   is the set  of  Nest[dsf,n,5]  for n = 110001 ~ 210000
                                                           ⋮

When q = 50       and  p =  501 d[501] is the set of  Nest[dsf,n,5]  for    n = 5010001~ 5020000
                                p =  502   d[502] is the set of  Nest[dsf,n,5]  for    n = 5020001~ 5030000
                               p =  503    d[503] is the set of  Nest[dsf,n,5]  for  n = 5030001~ 5040000
                                                                 ⋮
                               p =  510    d[510] is the set of  Nest[dsf,n,5]  for   n = 5100001~ 5110000
                          sd[50] is the union of d[501], d[502],  ⋯, d[510]  
                         Therefore sd[50]   is the set  of  Nest[dsf,n,5]  for  n = 5010001~ 5110000

ssd is the union of  sd[0], sd[1],⋯,sd[50].
       Therefore ssd is the set of  Nest[dsf,n,5] for  n = 10001~ 5110000

Now we can begin to prove Theorem 3.

Let us explain about the following programs we are going to use to prove Theorem 3.
(1) The list  elementsofloop  is the set of all the integers which belong to one of these 8 loops, i.e., elementsofloop=Join[loop1A,loop1B,loop2,loop3,loop8,loop11,loop40,loop97];

loop1A = {1};
loop1B = {3435};
loop2 = {421845123, 16780890};
loop3 = {16777500, 2520413, 3418};
loop8 = {809265896, 808491852, 437755524, 1657004, 873583, 34381154, 
          16780909, 792488396};
loop11 = {791621579, 776537851, 19300779, 776488094, 422669176, 
          388384265, 50381743, 17604196, 388337603, 34424740, 
          824599};
loop40 = {793312220, 388244100, 33554978, 405027808, 34381363, 
          16824237, 17647707, 3341086, 16824184, 33601606, 140025, 3388, 
          33554486, 16830688, 50424989, 791621836, 405114593, 387427281, 
          35201810, 16780376, 18517643, 17650825, 17653671, 1743552, 830081, 
          33554462, 53476, 873607, 18470986, 421845378, 34381644, 16824695, 
          404294403, 387421546, 17651084, 17650799, 776537847, 20121452, 
          3396, 387467199};
loop97 = {1583236420, 16827317, 18470991, 792441996, 1163132183, 
          16823961, 404291050, 387424134, 17601586, 17697199, 1163955211, 
          387473430, 18424896, 421022094, 387421016, 17647705, 2520668, 
          16873662, 17740759, 389894501, 808398820, 454529386, 404251154, 
          7025, 826673, 17694102, 388290951, 808398568, 454579162, 388297455, 
          421805001, 16780606, 17740730, 2470915, 388247419, 421799008, 
          792442000, 388244555, 33564350, 53244, 3668, 16870555, 17656792, 
          389164017, 405068190, 404247746, 1694771, 389114489, 808395951, 
          808401689, 437799052, 776491477, 390761830, 405067961, 388340728, 
          51155506, 59159, 774847229, 406668854, 33698038, 421021659, 
          387470537, 19251281, 404200841, 16777992, 777358268, 36074873, 
          18471269, 405068166, 16920568, 404294148, 404198735, 405024914, 
          387424389, 421799034, 775665066, 1839961, 791664879, 793358849, 
          809222388, 437752177, 3297585, 405027529, 388250548, 50338186, 
          33604269, 387514116, 17650826, 17697202, 389114241, 404198251, 
          404201349, 387421291, 405021541, 6770, 1693743, 
          388290999};
elementsofloop = 
        Join[loop1A, loop1B, loop2, loop3, loop8, loop11, loop40, 
          loop97];

Of course we are going to use the function  dsf.

Clear[dsf]; 
    dsf[n_] := Block[{m = n, t}, 
        t = IntegerDigits[
            m]; 
(∑_(k = 1)^(Length[t]))Max[1, t[[k]]]^t[[k]]]

(2) The Mathematica function gc[n]return the first integer of the loop into which the sequence{(dsf^m)[n],m = 1,2  ⋯}enters .   If we can prove that for any positive integer n  gc[n] belongs to the set  elementofloop,then we can finish the proof of Theorem 3.  
Note that the function  gc[n] is the same as  findloop[n][[3]].

gc[n_] := 
        Block[{m = n, u, dat}, dat = {m}; m = dsf[m]; 
          While[! MemberQ[dat, m], dat = Append[dat, m]; m = dsf[m]]; 
          dat = Append[dat, m]; Last[dat]];

(3) The function lookforloop [s] returns a list  q  =p - elementsofloop,where  p={gc[n];2500000  s ≤ n ≤ 
                    2500000 (s + 1)}.   If q={},then  p ⊂ elementsofloop, which implies that for any integer from 2500000s   to   2500000(s + 1) {(dsf^m)[n],m = 1,2  ⋯}eventually enters into one of these 8 loops .   In Lemma 6 and its proof we are going to explain about the function  lookforloop

lookforloop[s_] := 
      Block[{firststep, p, n, data, 
          u = s}, 
Do[
Do[
            firststep[p] = 
              Union[Table[
                  Nest[dsf, n, 5], {n, 500000  m + 10000  p + 1, 
                    500000  m + 10000  p + 10000}]], {p, 0, 
              49}]; 
data[m] = 
            Map[gc, Union[
                Flatten[
                  Table[firststep[t], 
{t, 0, 
                      49}]]]], 
{m, 5  s, 
            5  s + 4}]; 
ddata[s] = 
          Union[Flatten[
              Table[data[m], {m, 5  s, 
                  5  s + 4}]]]; 
Complement[ddata[s], 
          elementsofloop]]

Lemma 6. .  If lookforloop[s] returns the null set {},then for n=2500000  s+1 ~2500000(s + 1)  the sequence  {(dsf^m)[n],m = 1,2  ⋯} eventually enters into one of these 8 loops.

We use Mathematica to prove Lemma 6, so we are going to explain about the algorithm of function lookforloop.

We applied the dsf function 5 times to the set of numbers.  The reason why we applied 5 times is that it seemed to us the best option in terms of time consumption.  We used Do[ ] and Table[ ] together, because it seemed to be the best option for our computer in terms of the size of memory and time consumption.

When m = 5s    and  p = 0 , firststep[0] is the set of Nest[dsf,n,5] for  n = 500000×5s + 1              ~ 500000×5s + 10000
                               p = 1,  firststep[1] is the set of Nest[dsf,n,5] for  n = 500000×5s + 10001  ~ 500000×5s + 20000 
                               p = 2,  firststep[2] is the set of Nest[dsf,n,5] for  n = 500000×5s + 20001  ~  500000×5s + 30000
                                                  ⋮
                               p = 49,  firststep[49] is the set of Nest[dsf,n,5] for  n = 500000×5s + 490001 ~ 500000×5s + 500000
                         We make the Union of the sets  firststep[0], firststep[1], ⋯, firststep[49], and map the union by the function gc and we get  data[5s].
                         Therefore  data[5s] is the set of gc[Nest[dsf,n,5]]  for  n = 500000×5s + 1              ~       500000×5s + 500000

When m=5s +1   and p=0,  firststep[0] is the set of Nest[dsf,n,5] for  n=500000×(5s+1)+1 ~ 500000×(5s+1)+10000
                                p=1,  firststep[1] is the set of Nest[dsf,n,5] for  n=500000×(5s+1)+10001 ~ 500000×(5s+1)+20000
                                p=2,  firststep[2] is the set of Nest[dsf,n,5] for  n=500000×(5s+1)+20001 ~ 500000×(5s+1)+30000
                                                  ⋮
                                p=49,  firststep[49] is the set of Nest[dsf,n,5] for  n=500000×(5s+1)+490001 ~ 500000×(5s+1)+500000
                           We make the Union of the sets  firststep[0], firststep[1], ⋯, firststep[49], and map the union by the function gc and we get  data[5s+1].
                            Therefore  data[5s+1] is the set of gc[Nest[dsf,n,5]]  for  n = 500000×(5s+1)+1              ~       500000×(5s+1)+500000

⋮
We can do the same kind of calculation for m=5s+2, m=5s+3.

⋮
When m=5s +4   and p=0,  firststep[0] is the set of Nest[dsf,n,5] for  n=500000×(5s +4)+1 ~ 500000×(5s +4)+10000
                                p=1,  firststep[1] is the set of Nest[dsf,n,5] for  n=500000×(5s +4)+10001 ~ 500000×(5s +4)+20000
                                p=2,  firststep[2] is the set of Nest[dsf,n,5] for  n=500000×(5s +4)+20001 ~ 500000×(5s +4)+30000
                                                  ⋮
                                p=49,  firststep[49] is the set of Nest[dsf,n,5] for  n=500000×(5s +4)+490001 ~ 500000×(5s +4)+500000
                             We make the Union of the sets  firststep[0], firststep[1], ⋯, firststep[49], and map the union by the function gc and we get  data[5s+4].
                                Therefore  data[5s+4] is the set of gc[Nest[dsf,n,5]]  for  n =500000×(5s +4)+1 ~500000×(5s +4)+500000

ddata[s] is the Union of sets  data[5s], data[5s+1], data[5s+2], data[5s+3], data[5s+4].
Therefore ddata[s] is the set of   gc[Nest[dsf,n,5]] for n=500000×5s+1 ~500000×(5s+4)+500000= 500000×5(s+1)

If  Complement[ddata[s], elementsofloop] is null,  
    then each  gc[
          Nest[dsf, n, 
            5]] belongs to the set  elementsofloop  for n = 
      500000×5  s + 
        1 ~500000×5 (s + 1).

\(\(\(\ \)\(Therefore\ \ if\ \ lookforloop[s]\ returns\ \ {}, \ 
    then\ for\ n = 
      500000×5  s + 
        1\ ~500000×5 \((s + 1)\)\ \ the\ sequence\ \ {\(dsf\^m\)[n], 
            m = 1, 2  ⋯}\ eventually\ enters\ into\ one\ of\ the\ \(\(loops\)\(.\)\)\)\)\)

Lemma 7.  We can calculate   lookforloop[s]  for n=1 ~
          1405 by the following program.

Do[star = 
        40  nn; 
Do[
Do[
Clear[ddata]; Print[st]; 
          Print[lookforloop[st]], {st, 5  kk + 1, 5  kk + 5}]; 
        Print[kk], {kk, star, 
          star + 10}]; 
Do[
Do[
Clear[ddata]; Print[st]; 
          Print[lookforloop[st]], {st, 5  kk + 1, 5  kk + 5}]; 
        Print[kk], {kk, star + 11, 
          star + 20}]; 
Do[
Do[
Clear[ddata]; Print[st]; 
          Print[lookforloop[st]], {st, 5  kk + 1, 5  kk + 5}]; 
        Print[kk], {kk, star + 21, 
          star + 30}]; 
Do[
Do[
Clear[ddata]; Print[st]; 
          Print[lookforloop[st]], {st, 5  kk + 1, 5  kk + 5}]; 
        Print[kk], {kk, star + 31, star + 40}], {nn, 0, 6}]

We use Mathematica to prove Lemma 7, so we are going to explain about the algorithm of the above program. We are going to write down the procedure, but we omit the part where we use the same kind of calculation over and over again.

(0) When nn = 0, then  star = 0.   
(a) In the first Do[ Do[]]-loop  when  kk = 0, st = 1 ~ 5
                                 when  kk = 1, st = 6 ~ 10
                                 when  kk = 2, st = 11 ~ 15
                                            ⋮
                                 when  kk = 10, st = 51 ~ 55
(b) In the second Do[ Do[]]-loop when  kk = 11, st = 56 ~ 60
                                 when  kk = 12, st = 61 ~ 65
                                 when  kk = 13, st = 66 ~ 70
                                            ⋮
                                 when  kk = 20, st = 101 ~ 105
(c) In the third Do[ Do[]]-loop  when  kk = 21, st = 106 ~ 110
                                 when  kk = 22, st = 111 ~ 115
                                 when  kk = 23, st = 116 ~ 120
                                            ⋮
                                 when  kk = 30, st = 151 ~ 155
(d) In the forth Do[ Do[]]-loop  when  kk = 31, st = 156 ~ 160
                                 when  kk = 32, st = 161 ~ 165
                                 when  kk = 33, st = 166 ~ 170
                                            ⋮
                                 when  kk = 40, st = 201 ~ 205     
(1) When nn = 1, then  star = 40.   
(a) In the first Do[ Do[]]-loop  when  kk = 40, st = 201 ~ 205
                                 when  kk = 41, st = 206 ~ 210
                                 when  kk = 42, st = 211 ~ 215
                                            ⋮
                                 when  kk = 50, st = 251 ~ 255  
                                            ⋮      
(d) In the forth Do[ Do[]]-loop  when  kk = 71, st = 356 ~ 360
                                 when  kk = 72, st = 361 ~ 365
                                 when  kk = 73, st = 366 ~ 370
                                            ⋮
                                 when  kk = 80, st = 401 ~ 405
                                            ⋮   
(6) When nn = 6, then  star = 240.   
(a) In the first Do[ Do[]]-loop  when  kk = 240, st = 1201 ~ 1205
                                 when  kk = 241, st = 1206 ~ 1210
                                 when  kk = 242, st = 1211 ~ 1215
                                            ⋮
                                 when  kk = 250, st = 1251 ~ 1255  
                                            ⋮      
(d) In the forth Do[ Do[]]-loop  when  kk = 271, st = 1356 ~ 1360
                                 when  kk = 272, st = 1361 ~ 1365
                                 when  kk = 273, st = 1366 ~ 1370
                                            ⋮
                                 when  kk = 280, st = 1401 ~ 1405

(4) By the above program we applied the function lookforloop[s] to the list {s;1≤s≤1405}, and we also calculated  lookforloop[0]. Note that by using only the above program we cannot get lookforloop[0]. In both case we get {} for each s.  Therefore  we can finish the proof of Theorem 3, because 2500000×(1405+1)=3515000000>3000000000 and by Theorem 1 we do not have to worry about integers bigger than 3000000000. 
    You may think that we are calculating for numbers well above 3000000000, and by doing this spending time and enegy which are useless.  We did this, because we wanted to make our algorithm simpler.

3.  A smaller universe; the dsf process for smaller numbers.

For any integer  K  we define the function dsfK  by  dsfK[n]= Mod[(Subscript[((Subscript[n, 1])^n), 1]) + (Subscript[((Subscript[n, 2])^n), 2]) + ⋯(Subscript[((Subscript[n, m])^n), m]), 
            K] ,where  {(Subscript[n, 1]), (Subscript[n, 2]), ⋯, (Subscript[n, m]) } is \(TraditionalForm\`\(\(\ \ \)\(\(the\)\(\ \ \)\(list\)\(\ \)\(of\)\(\ \)\(the\)\(\ \)\(digits\)\(\ \)\(of\)\(\ \)\(an\)\(\ \)\(integer\)\(\ \)\)\)\)n  .   We call the process made by the dsfK function  the dsfK process .    It is ofthen the case that  the dsfK process share many features with the original dsf process, but many theorems are easier to prove in the dsfK  when  the integer  K is small enough .   Therefore the dsfK is important for two reasons . One is that we can prove theorems first in the dsfK, and afterwards try to find the same kind of theorems in the original dsf process .   The dsfK gives us the chance many kind of predictions without using too much time .   In fact we could prove some curious fact  in dsf5000 process .   The other reason is that it will make a very good courseware for students .   Students can enjoy proving many things without worrying about the time and memory they are going to use .   
In a sense this dsfK process is a small universe which shares many theorems with the dsfK process which is a bigger universe.

In Section 3 we let  K = 5000, and are going to study dsf5000 process.  Let  T = {0,1,2,⋯,4999}.

First we make the Mathematica function  dsf5000.

Clear[dsf5000]; 
    dsf5000[n_] := 
      Block[{m = n, t}, 
        t = IntegerDigits[
            m]; 
Mod[(∑_(k = 1)^(Length[t]))Max[1, t[[k]]]^t[[k]], 5000]];

The Mathematica function  findloop5000[n] returns   a list of numbers{n, p, t, q} .   We start with the number  n, then the sequence (dsf5000^m)[n] enters into a loop when m = p, and  (dsf5000^p)[n] =t .   The length of the loop is  q and  (dsf5000^(p + q))[n]=t=(dsf5000^p)[n].

findloop5000[n_] := 
        Block[{m = n, u, dat}, dat = {m}; m = dsf5000[m]; 
          While[! MemberQ[dat, m], dat = Append[dat, m]; m = dsf5000[m]]; 
          dat = Append[dat, m]; 
          u = Flatten[Position[dat, Last[dat]]]; {n, u[[1]] - 1, 
            Last[dat], u[[2]] - u[[1]]}];

Example 8.  If we calculate  findloop5000[2] then , we get {2, 26, 2271, 
            8} .   This means that if we start with 1000, after  we apply dsf5000  6 times  enters into a loop after  26 steps  with the length of 8.

findloop5000[2]

Example 9.  If we apply findloop5000 to the set of numbers  {1, 2, ⋯, 15} , then we have the following list of numbers .  
          As to the length of loops we found 1,3, 8 and 12.

Table[findloop5000[n], {n, 1, 15}]

Theorem 4.　Let K=5000,then for any positive integer n∈{0, 1, 2, ⋯, 4999} the sequence {(dsfK^m)[n],m = 1,2  ⋯}eventually enters into one of the following 8 loops   loop1A,loop1B,loop1C,loop1D,loop1E,loop3,loop8  and  loop12.

(1) loop1A ={1} with the length of 1, i.e., a fixed point.
(2) loop1B ={1255} with the length of 1.
(3) loop1C ={2228} with the length of 1.
(4) loop1D ={3366} with the length of 1.
(5) loop1E ={3435} with the length of 1.
(6) loop3 ={13,28,2220} with the length of 3.
(7) loop8 ={16,1657,3325,3183,2271,3552,1281,2222} with the length of 8.
(8) loop12 ={56,4781,1016,1659,271,3548,624,1916,2147,3804,2500,3131} with the length of 12.
Remark.loop1A,loop1B,loop1C,loop1D and loop1E are so called fixed points.

We are going to prove this by the calculation of Mathematica.  We are going to use almost the same method we used for Theorem 3.  We need Lemma 8 and Lemma 9 to prove Theorem 3.  In fact we can do without Lemma 9, because we are dealing with T = {0,1,2,⋯,4999} and the size of  T is small, however, we use Lamma 9 to make the reader understand the proof of Theorem 3.

Lemma 8. loop1A ={1},loop1B ={1255},loop1C ={2228},loop1D ={3366},loop1E ={3435},loop3 ={13,28,2220},loop8 ={16,1657,3325,3183,2271,3552,1281,2222},loop12 ={56,4781,1016,1659,271,3548,624,1916,2147,3804,2500,3131,
    56} are loops.

\(Proof . \ \ We\ can\ prove\ this\ by\ the\ calculation\ using\ Mathematica . \ \ For\ example\ the\ following\ calculation\ shows\ that\ loop8 = {16, 1657, 3325, 3183, 2271, 3552, 1281, 2222, 
          16}\ is\ a\ loop . \ \ We\ can\ easily\ prove\ the\ same\ thing\ for\ other\ loops, \ 
    so\ we\ omit\ the\ proofs\ of\ \(\(them\)\(.\)\)\)

We define the set elementofloop5000 as a union of all the loops.

loop1A = {1}; loop1B = {1255}; loop1C = {2228};  
    loop1D = {3366}; loop1E = {3435};  loop3 = {13, 28, 2220} ; 
    loop8 = {16, 1657, 3325, 3183, 2271, 3552, 1281, 2222};  
    loop12 = {56, 4781, 1016, 1659, 271, 3548, 624, 1916, 2147, 3804, 2500, 
        3131};
elementofloop5000=Join[loop1A, loop1B, loop1C, loop1D, loop1E, loop3, loop8, 
          loop12];

Lemma 9. Let  T ={0, 1, 2, ⋯, 4999}.   (dsf5000^5)[T]is a set  of the size of 155.  Note that the size of the set data1=(dsf5000^5)[T]  is quite small compared to the original set  T.

data5 = Union[Table[Nest[dsf5000, n, 5], {n, 0, 4999}]];

The following list data1 is the set (dsf5000^5)[
          T].

data5

Length[data5]

The proof of Theorem 4.

The following Mathematica function gc5000[n]return the first integer of the loop into which the sequence{(dsf5000^m)[n],m = 1,2  ⋯}enters .   Note that The function  gc5000[n] is the same as  findloop5000[n][[3]].  If we can prove that for any  n∈T = {0, 1, 2, ⋯, 4999}  gc5000[n] ∈  elementofloop5000,then we can finish the proof of Theorem 4, but by Lemma 9  we only have to prove that  any  n∈(dsf5000^5)[T]  gc5000[n]∈ elementofloop5000.

gc5000[n_] := 
        Block[{m = n, u, dat}, dat = {m}; m = dsf5000[m]; 
          While[! MemberQ[dat, m], dat = Append[dat, m]; m = dsf5000[m]]; 
          dat = Append[dat, m]; Last[dat]];

d = Union[Table[gc5000[data5[[n]]], {n, 1, 155}]]

Complement[d,elementofloop5000]

We have proved that gc5000[data5]⊂elementofloop5000.  Therefore we have proved  Theorem 4.

4.  Some curious properties of the  loops of the smaller universe.

By Theorem 4 we know that there are 4 fixed points and loops of the length of 3, \(8\ and\ 12. \ \ We\ are\ going\ to\ study\ these\ loops\ more\ carefully . \ \ What\ we\ could\ find\ about\ \ dsf5000\ process\ can\ be\ generalized\ to\ the\ facts\ about\ \ dsf\ process\), \(but\ it\ will\ need\ a\ lot\ of\ time\ to\ \(\(calculate\)\(.\)\)\)

We denote the set {n,(dsfK^m)[n]eventually enters into loop1A} by toloopA.  Similary we use toloop1A ,to  loop1B,to  loop1C,to  loop1D,to  loop1E,to  loop3 and to  loop12  for loops  loop1A ,loop1B,loop1C,loop1D,loop1E,loop3 and  loop12 .

Example 10.  We are going to study the set toloop8.  It is easy to get toloop8.

data5000 = 
        Table[findloop5000[n], {n, 0, 
            4999}];
loopof8 = 
        Select[data5000, #[[4]] == 8 &];
toloop8=Map[#[[1]] &, loopof8];

By calcutating the size of toloop8 we know that the great majority of numbers in  T ={0, 1, 2, ⋯, 4999} belong to toloop8.  We can also see this fact by using ListPlot[ ] .   Since the graph is almost linear, we see that the set  toloop8 is quite dense in  the set  T as a subset.

Length[toloop8]

ListPlot[toloop8]

Example 11.  We are going to study  loops  loop3 and loop12 .  We  calculate the size of the sets  toloop3  and  toloop12.  As you can see in the following calculation, the size of  toloop12 is relatively big compared to  toloop3, but they both are small compared to  toloop8.

data5000 = Table[findloop5000[n], {n, 0, 4999}];

loopof12 = 
        Select[data5000, #[[4]] == 
              12 &];
loopof3 = 
        Select[data5000, #[[4]] == 3 &];
toloop12=Map[#[[1]] &, loopof12];
toloop3=Map[#[[1]] &, loopof3];
Print["the size of toloop12 is ", 
      Length[toloop12]]
Print["the size of \
toloop3 is ", Length[toloop3]]

Example 12.  We are going to study the size of  the sets   toloop1A ,toloop1B,toloop1C,toloop1D,toloop1E.  Among these sets  toloop1E  is biggest.

data5000 = Table[findloop5000[n], {n, 0, 4999}];

fixedpoints = {{toloop1A, 1}, {toloop1B, 1255}, {toloop1C, 
          2228}, {toloop1D, 3366}, {toloop1E, 3435}}; 
    Do[fix = Select[
          data5000, #[[4]] == 1 && #[[3]] == 
                fixedpoints[[n, 2]] &]; 
tofix = 
        Map[#[[1]] &, fix]; 
Print["the size of ", 
        fixedpoints[[n, 1]], " is  ", Length[tofix]], {n, 1, 
        5}]

The function  findloop5000[n] returns   a list of numbers{n, p, t, q} .   We start with the number  n, then the sequence (dsf5000^m)[n] enters into a loop when m = p, and  (dsf5000^p)[n] =\(t . \ \ We\ call\ t\ the\ gate\ of\ the\ \(\(loop\)\(.\)\(\ \ \)\)\)

Example 13.   There are 8 gates for loop8, since the length of loop8  is 8.   Here we are going to study two of them  2271 and 16.  We denote by togate2271 the set {n,(dsfK^m)[n]eventually enters into loop8 by the gate 2271}.  We found out that the size of the set  togate2271  is 3944.  This fact is remarkable .   This means that  3944 numbers  out of 5000 numbers  enter the loop8 by the gate 2271!

data5000 = Table[findloop5000[n], {n, 0, 4999}];

gate2271 = 
        Select[data5000, #[[4]] == 8 && #[[3]] == 
                2271 &];
togate2271=Map[#[[1]] &, gate2271];
Length[togate2271]

gate16 = 
        Select[data5000, #[[4]] == 8 && #[[3]] == 
                16 &];
togate16=Map[#[[1]] &, gate16];
Length[togate16]

Remark .   We can make many kind process which is similar to ours .   For example we can define a function  by  dsf2[n]= (Subscript[((Subscript[n, 1])^n), m]) + 
          (Subscript[((Subscript[n, 2])^n), m-]) + ⋯(Subscript[((Subscript[n, m])^n), 1]),where  {(Subscript[n, 1]), (Subscript[n, 2]), ⋯, (Subscript[n, m]) } is \(TraditionalForm\`\(\(\ \ \)\(\(the\)\(\ \ \)\(list\)\(\ \)\(of\)\(\ \)\(the\)\(\ \)\(digits\)\(\ \)\(of\)\(\ \)\(an\)\(\ \)\(integer\)\(\ \)\)\)\)n  .   We have not studied this dsf2 function.

Robert Cowen  and John W.Kennedy   [1].Discovering Mathematics with Mathematica rudition Books   2001.